import java.lang.reflect.Array;
import java.util.Arrays;

public class Heap {
    private int[] elem;
    private int Usedsize;
    public Heap(){
        elem = new int[30];
    }
    //初始化
    public void initHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            Usedsize++;
        }
    }
    //建堆
    public void CreatHeap(){
        for (int parent = (Usedsize-1-1) / 2;parent >= 0;parent--){
            shiftDown(parent,Usedsize);
        }
    }
    private void Swap(int i,int j){
        int t = elem[i];
        elem[i]=elem[j];
        elem[j] = t;
    }
    //向下调整
    private void shiftDown(int parent,int useSize){
        int child = parent*2 + 1;
        while(child < useSize){
            if(child+1 < useSize && elem[child] < elem[child-1]){
                child++;
            }
            //child已经是两个孩子中较大的了
            if(elem[parent] < elem[child]){
                Swap(parent,child);
                parent = child;
                //默认为左孩子
                child = parent*2 + 1;
            }else {
                break;
            }
        }
    }
    //打印
    public void Display(){
        for (int i = 0; i < Usedsize; i++) {
            System.out.print(elem[i] + " ");
        }
    }
    //添加
    public void offer(int val){
        if(Isfull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[Usedsize] = val;
      shiftUp(Usedsize);
        Usedsize++;
    }
//向上调整
    private void shiftUp(int usedsize) {
        int child = usedsize;
        int parent = (child-1)/2;
        while (child < 0){
            if(elem[child] > elem[parent]){
                Swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    //弹出
    public int pop(){
        int tmp = elem[0];
        Swap(0,Usedsize-1);
        Usedsize--;
        shiftDown(0,Usedsize);
        return tmp;
    }
//判满
    private boolean Isfull(){
        return Usedsize == elem.length;
    }
}
